“Digital goods” is a generic label for electronically stored or transmitted content. Examples of digital goods include images, audio clips, video, multimedia, software, and data. Digital goods may also be called a “digital signal,” “content signal,” “digital bitstream,” “media signal,” “digital object,” “object,” and the like.
Digital goods are often distributed to consumers over private and public networks—such as Intranets and the Internet. In addition, these goods are distributed to consumers via fixed computer readable media, such as a compact disc (CD-ROM), digital versatile disc (DVD), soft magnetic diskette, or hard magnetic disk (e.g., a preloaded hard drive).
Unfortunately, it is relatively easy for a person to pirate the pristine digital content of a digital good at the expense and harm of the content owners—which includes the content author, publisher, developer, distributor, etc. The content-based industries (e.g., entertainment, music, film, etc.) that produce and distribute content are plagued by lost revenues due to digital piracy.
Modern digital pirates effectively rob content owners of their lawful compensation. Unless technology provides a mechanism to protect the rights of content owners, the creative community and culture will be impoverished.
Watermarking
Watermarking is one of the most promising techniques for protecting the content owner's rights of a digital good. Generally, watermarking is a process of altering the digital good such that its perceptual characteristics are preserved. More specifically, a “watermark” is a pattern of bits inserted into a digital good that may be used to identify the content owners and/or the protected rights.
Generally, watermarks are designed to be completely invisible or, more precisely, to be imperceptible to humans and statistical analysis tools.
A watermark embedder (i.e., encoder) is used to embed a watermark into a digital good. A watermark detector is used to extract the watermark from the watermarked digital good. Watermark detection is performed in real-time even on small devices.
Those of ordinary skill in the art are familiar with conventional techniques and technology associated with watermarks, watermark embedding, and watermark detecting.
Watermarks have limitations. They may be used to designate a digital good as protected and, perhaps, to indicate that a license is necessary to legally use the digital good. However, since watermarks are identical in all copies of a digital good, a digital pirate can reproduce the original content of a marked copy by breaking the watermark at a single watermark detector, for example by extracting the detection key and using it to find the watermark and remove it or jam it.
Therefore, others may use the original content without the watermark; thus, without the content owner receiving the appropriate compensation. This is generally called “break once run everywhere” or BORE.
Furthermore, to individualize a particular copy of a digital good (or a particular system that will use that good) with watermarks, we need to augment it with a technology called “fingerprinting”.
Conventional Fingerprinting
Conventional fingerprinting (i.e., “classic fingerprinting”) refers to techniques that involve uniquely marking each copy of a particular digital good, and associating each uniquely marked copy with a “classic fingerprint.” That classic fingerprint is associated with or assigned to a particular entity (e.g., person, business, media player, or smart card) to which the copy is distributed.
If unauthorized copies of the uniquely marked copy are made, the fingerprint can be traced back to the original entity to which the copy was initially distributed. In other words, classic fingerprinting technology may be used to trace piracy to its origin.
As an example, consider a printed map. When a mapmaker produces a map, they may want to ensure that those individuals to whom the map is distributed do not make unauthorized copies of the map and distribute them to others. One way that the mapmaker might protect his maps is to introduce a different trivial error (e.g., a non-existent street) into each of the copies of the map that are distributed. Those different trivial errors are fingerprints. Each fingerprint is then associated with an individual to whom the map is distributed. By associating each different fingerprint with a different individual, if and when unauthorized copies of that individual's copy are uncovered, they can be traced back to the original individual by virtue of the unique fingerprint that the map contains.
Using embedding methods similar (but not identical) to watermarking, the fingerprint is embedded into a digital good. If we want to achieve both prevention and “after the fact” tracing, a combination of the fingerprint and watermark are embedded into a digital good.
Very powerful machines that can devote significant resources to the process of detecting a fingerprint typically perform fingerprint detection. If necessary, a fingerprint detector can have access to the original unmarked digital good, using it to improve the likelihood of success in detecting the fingerprints—even from content modified by malicious attacks.
Classic Fingerprint=Unique Entity Identifier (UEid)
Although the term “fingerprint” is commonly understood by those of ordinary skill in the art, the terms “classic fingerprint” or “unique entity identifier” (UEid) may be used hereinafter to refer to this conventional technology (and its unique marks). This is done to avoid confusion with the use, herein, of “fingerprinting” in the other sections of this document (i.e., sections other than the “Background” section). In those other sections, the term “fingerprinting” may refer to a similar, but distinctly different technology.
Collusion
One problem with fingerprinting can arise when two or more entities collude. Their purpose for doing this may be to discover, modify, or remove their fingerprints and/or the embedded watermark. Those that attempt to collude are called “colluders.” A group of colluders who attempt to collude are part of a “collusion clique.”
Returning to the map example for illustration, collusion occurs when two or more individuals get together and compare their maps. They can, given enough time, ascertain their unique fingerprints by simply looking for the differences between their maps. If they can ascertain their fingerprint, they can alter it and therefore possibly avoid detection.
With the advent of the Internet and electronic distribution, fingerprinting digital goods for purposes of detecting or deterring unauthorized copying has become particularly important. As in the above map example, collusion by different individuals in the digital context can pose challenges to the owners and distributors of digital goods.
Conventional Fingerprinting/Watermarking Systems with Collusion Resistance
Existing conventional fingerprinting/watermarking systems have some capability for collusion detection. However, the protection offered by these systems is limited.
For example, Ergun et al. have proved that no conventional fingerprinting system can have a better asymptotical collusion-resistance than: O((N/log(N))1/2)—where O indicates “order of magnitude” and N is the size of the marked digital good. For example, the best fingerprinting system today, “the Improved Boneh Shaw System” achieves for a typical two hour movie a collusion resistance of only 40 users. This system, just as the original “Boneh Shaw Fingeprinting System” has collusion resistance in the order of O(N1/4).
The derivation of the upper bound on fingerprinting mechanisms by Ergun et al. considers embedding distinct fingerprints per copy of a digital good and models collusion attacks as averaging of copies with additive noise. Aspects of their work are described in an article entitled “A Note on the Limits of Collusion-Resistant Watermarks,” authored by Ergun, Kilian, and Kumar, appearing in Proc. Eurocrypt, 1999.
For example, another conventional fingerprinting system (the “Boneh-Shaw, or B-S system”) defines a lower bound on collusion-resistant fingerprinting: O(N1/4). Assuming that the marked digital good is a typical music clip, the lower bound of the number of colluders necessary to thwart this conventional system is in the neighborhood of 4. The B-S system is a fingerprinting system that attempts to overcome the problem of collusion when fingerprinting digital goods. Aspects of the B-S system are described in an article entitled “Collusion-Secure Fingerprinting for Digital Data” authored by Boneh and Shaw, appearing in IEEE Transactions on Information Theory, Vol. 44, No. 5, September 1998.
Those of ordinary skill in the art are familiar with conventional techniques and technology associated with classic fingerprinting, classic fingerprinting embedding, and classic fingerprinting detecting.
Although the conventional fingerprinting systems provide some protection against collusion, that protection is only effective when the number of colluders is relatively small. Consequently, the confidence level that a marked digital good is free from the effects of collusion is not high.
Accordingly, there is a need for a new watermarking/fingerprinting technology that is more collusion resistant. A new technology is needed that increases the protection that is provided by fingerprinting (and watermarking) to detect colluders even when their numbers are large. If that numbers is several orders of magnitude greater than the conventional, then the confidence level—that a marked digital good is free from the effects of collusion—would be very high indeed.
Moreover, there needs to be a more effective technique to identify that a digital good has had its mark removed and who removed that mark. That way, piracy crimes can be more effectively investigated.